/*
 * @Author: YiY
 * @Date: 2024-01-08 09:04:11
 * @LastEditTime: 2024-01-08 09:25:14
 */
function insert(list, i, j) {
  let x = list.splice(j, 1)
  list.splice(i, 0, x[0])
  return list
}

function shellSort(arr) {
  let n = arr.length;
  let gap = Math.floor(n / 2);

  while (gap > 0) {
    for (let i = gap; i < n; i++) {
      let temp = arr[i];
      let j = i;
      while (j >= gap && arr[j - gap] > temp) {
        arr[j] = arr[j - gap]
        j -= gap
      }
      arr[j] = temp;
    }
    gap = Math.floor(gap / 2);
  }

  return arr;
}

// 测试数据
let arr = [9, 8, 7, 6, 5, 4, 3, 2, 1];
console.log("原始数组：", arr);
console.log("希尔排序后：", shellSort(arr));
